package com.breeze.leetcode.easy;

import java.util.Arrays;

/**
 * @author breeze
 * @url <a href="https://leetcode.cn/problems/count-pairs-of-similar-strings">2506. 统计相似字符串对的数目</a>
 * @date 2025/2/22
 */
public class T2506 {
    public static void main(String[] args) {
        String[] words = {"nba","cba","dba"};
        T2506 solution = new T2506();
        System.out.println(solution.similarPairs(words));
    }

    public int similarPairs(String[] words) {
        if (words.length == 1) {
            return 0;
        }

        int res = 0;
        String[] memo = new String[words.length];
        for (int i = 0; i < words.length - 1; i++) {
            String current = "";
            if (memo[i] != null) {
                current = memo[i];
            } else {
                current = removeDuplicate(words[i]);
                memo[i] = current;
            }

            for (int j = i + 1; j < words.length; j++) {
                if (memo[j] != null && memo[j].equals(current)) {
                    res++;
                } else {
                    String cursor = removeDuplicate(words[j]);
                    memo[j] = cursor;
                    if (current.equals(cursor)) {
                        res++;
                    }
                }
            }
        }

        return res;
    }

    public String removeDuplicate(String word) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        StringBuilder res = new StringBuilder(String.valueOf(chars[0]));
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] > chars[i - 1]) {
                res.append(chars[i]);
            }
        }
        return res.toString();
    }
}
